{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Student that Will Replace the Chalk"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #prefix-sum #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #前缀和 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: chalkReplacer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到需要补充粉笔的学生编号"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个班级里有&nbsp;<code>n</code>&nbsp;个学生，编号为 <code>0</code>&nbsp;到 <code>n - 1</code>&nbsp;。每个学生会依次回答问题，编号为 <code>0</code>&nbsp;的学生先回答，然后是编号为 <code>1</code>&nbsp;的学生，以此类推，直到编号为 <code>n - 1</code>&nbsp;的学生，然后老师会重复这个过程，重新从编号为 <code>0</code>&nbsp;的学生开始回答问题。</p>\n",
    "\n",
    "<p>给你一个长度为 <code>n</code>&nbsp;且下标从 <code>0</code>&nbsp;开始的整数数组&nbsp;<code>chalk</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;。一开始粉笔盒里总共有&nbsp;<code>k</code>&nbsp;支粉笔。当编号为&nbsp;<code>i</code>&nbsp;的学生回答问题时，他会消耗 <code>chalk[i]</code>&nbsp;支粉笔。如果剩余粉笔数量 <strong>严格小于</strong>&nbsp;<code>chalk[i]</code>&nbsp;，那么学生 <code>i</code>&nbsp;需要 <strong>补充</strong>&nbsp;粉笔。</p>\n",
    "\n",
    "<p>请你返回需要 <strong>补充</strong>&nbsp;粉笔的学生 <strong>编号</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>chalk = [5,1,5], k = 22\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>学生消耗粉笔情况如下：\n",
    "- 编号为 0 的学生使用 5 支粉笔，然后 k = 17 。\n",
    "- 编号为 1 的学生使用 1 支粉笔，然后 k = 16 。\n",
    "- 编号为 2 的学生使用 5 支粉笔，然后 k = 11 。\n",
    "- 编号为 0 的学生使用 5 支粉笔，然后 k = 6 。\n",
    "- 编号为 1 的学生使用 1 支粉笔，然后 k = 5 。\n",
    "- 编号为 2 的学生使用 5 支粉笔，然后 k = 0 。\n",
    "编号为 0 的学生没有足够的粉笔，所以他需要补充粉笔。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>chalk = [3,4,1,2], k = 25\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>学生消耗粉笔情况如下：\n",
    "- 编号为 0 的学生使用 3 支粉笔，然后 k = 22 。\n",
    "- 编号为 1 的学生使用 4 支粉笔，然后 k = 18 。\n",
    "- 编号为 2 的学生使用 1 支粉笔，然后 k = 17 。\n",
    "- 编号为 3 的学生使用 2 支粉笔，然后 k = 15 。\n",
    "- 编号为 0 的学生使用 3 支粉笔，然后 k = 12 。\n",
    "- 编号为 1 的学生使用 4 支粉笔，然后 k = 8 。\n",
    "- 编号为 2 的学生使用 1 支粉笔，然后 k = 7 。\n",
    "- 编号为 3 的学生使用 2 支粉笔，然后 k = 5 。\n",
    "- 编号为 0 的学生使用 3 支粉笔，然后 k = 2 。\n",
    "编号为 1 的学生没有足够的粉笔，所以他需要补充粉笔。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>chalk.length == n</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= chalk[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-student-that-will-replace-the-chalk](https://leetcode.cn/problems/find-the-student-that-will-replace-the-chalk/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-student-that-will-replace-the-chalk](https://leetcode.cn/problems/find-the-student-that-will-replace-the-chalk/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,1,5]\\n22', '[3,4,1,2]\\n25']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        k %= sum(chalk)\n",
    "        # res = -1\n",
    "        # for i, v in enumerate(chalk):\n",
    "        #     if v > k:\n",
    "        #         res = i\n",
    "        #         break\n",
    "        #     k -= v\n",
    "        # return res\n",
    "\n",
    "        l, r = 0, len(chalk)\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            if sum(chalk[:m]) > k:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        k %= sum(chalk)\n",
    "        l, r = 0, len(chalk)\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            if sum(chalk[:m]) > k:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        k %= sum(chalk)\n",
    "        l, r = 0, len(chalk)\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            if sum(chalk[:m]) > k:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        k %= sum(chalk)\n",
    "        # res = -1\n",
    "        # for i, v in enumerate(chalk):\n",
    "        #     if v > k:\n",
    "        #         res = i\n",
    "        #         break\n",
    "        #     k -= v\n",
    "        # return res\n",
    "        l, r = 0, len(chalk)\n",
    "        while l < r:\n",
    "            m = (l + r) // 2\n",
    "            if sum(chalk[:m]) > k:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return l-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        su = sum(chalk)\n",
    "        yu = k % su\n",
    "        for i in range(len(chalk)):\n",
    "            if chalk[i] > yu:\n",
    "                return i\n",
    "            yu -= chalk[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        s = sum(chalk)\n",
    "        t = k % s\n",
    "        l = len(chalk)\n",
    "        for i in range(l):\n",
    "            t -= chalk[i]\n",
    "            if t < 0:\n",
    "                res = i\n",
    "                break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        n = len(chalk)\n",
    "        k %= sum(chalk)\n",
    "        for i in range(n):\n",
    "            if k < chalk[i]:\n",
    "                return i\n",
    "            else:\n",
    "                k -= chalk[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        k = k%sum(chalk)\n",
    "        i = 0\n",
    "        while i < len(chalk):\n",
    "            if k < chalk[i]:\n",
    "                return i \n",
    "            k -= chalk[i]\n",
    "            i += 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        rest = k % sum(chalk)\n",
    "        for i, n in enumerate(chalk):\n",
    "            if rest < n:\n",
    "                return i\n",
    "            rest -= n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        k %= sum(chalk)\n",
    "        print(k)\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        for i, v in enumerate(chalk):\n",
    "            k -= v\n",
    "            if k < 0:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        s = sum(chalk)\n",
    "        k %= s\n",
    "        i = 0\n",
    "        while k:\n",
    "            if k < chalk[i]:\n",
    "                return i\n",
    "            k -= chalk[i]\n",
    "            i += 1\n",
    "        return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        k = k % sum(chalk)\n",
    "        for i,x in enumerate(chalk):\n",
    "            if k < x: return i\n",
    "            k -= x\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        round = k // sum(chalk)\n",
    "        remaining = k - round * sum(chalk)\n",
    "        for i in range(len(chalk)):\n",
    "            remaining -= chalk[i]\n",
    "            if remaining < 0:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        x = k%sum(chalk)\n",
    "        for i, j in enumerate(chalk):\n",
    "            x -= j\n",
    "            if x < 0:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        k %= sum(chalk)\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        for i, num in enumerate(chalk):\n",
    "            k -= num\n",
    "            if k < 0: return i\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        using_sum = sum(chalk)\n",
    "        k = k % using_sum\n",
    "        for i in range(len(chalk)):\n",
    "            if k < chalk[i]:\n",
    "                return i\n",
    "            k -= chalk[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        s = sum(chalk)\n",
    "        res = k % s\n",
    "        for i in range(len(chalk)):\n",
    "            if res - chalk[i] < 0:\n",
    "                return i\n",
    "            else:\n",
    "                res -= chalk[i]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        total = sum(chalk)\n",
    "        k %= total\n",
    "        res = -1\n",
    "        for i, count in enumerate(chalk):\n",
    "            if count > k:\n",
    "                res = i\n",
    "                break\n",
    "            k -= count\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        s = sum(chalk)\n",
    "        ret = k % s\n",
    "        n = len(chalk)\n",
    "        for ans in range(n):\n",
    "            if ret < chalk[ans]:\n",
    "                return ans\n",
    "            ret -= chalk[ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        total = sum(chalk)\n",
    "        k %= total\n",
    "        res = -1\n",
    "        for i, cnt in enumerate(chalk):\n",
    "            if cnt > k:\n",
    "                res = i\n",
    "                break\n",
    "            k -= cnt\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        i = 0\n",
    "        k = k%(sum(chalk))\n",
    "        while 1:\n",
    "            if k < chalk[i]:\n",
    "                break\n",
    "            k -= chalk[i]\n",
    "            i = (i+1)%(len(chalk))\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        oneCycle = sum(chalk)\n",
    "        k -= k // oneCycle * oneCycle\n",
    "        i = 0\n",
    "        while k >= chalk[i]:\n",
    "            k -= chalk[i]\n",
    "            i += 1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        k %= sum(chalk)\n",
    "        for i, n in enumerate(chalk):\n",
    "            if k < n:\n",
    "                return i\n",
    "            k -= n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        # 先模拟\n",
    "        n = len(chalk)\n",
    "        k %= sum(chalk)\n",
    "        if k == 0: return 0\n",
    "\n",
    "        for i, c in enumerate(chalk):\n",
    "            k -= c\n",
    "            if k < 0:\n",
    "                return i\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        sum1 = sum(chalk)\n",
    "        k %= sum1 \n",
    "        while True:\n",
    "            for i,v in enumerate(chalk):\n",
    "                if k - v < 0:\n",
    "                    return i\n",
    "                k-=v\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        n = len(chalk)\n",
    "        if chalk[0] > k:\n",
    "            return 0\n",
    "        for i in range(1, n):\n",
    "            chalk[i] += chalk[i - 1]\n",
    "            if chalk[i] > k:\n",
    "                return i\n",
    "\n",
    "        k %= chalk[-1]\n",
    "        return bisect_right(chalk, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        total = sum(chalk)\n",
    "        k %= total\n",
    "        res = -1\n",
    "        for i, cnt in enumerate(chalk):\n",
    "            if cnt > k:\n",
    "                res = i\n",
    "                break\n",
    "            k -= cnt\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        per_epi_num = sum(chalk)\n",
    "        k_ = k % per_epi_num\n",
    "        for i, ch in enumerate(chalk):\n",
    "            k_ -= ch\n",
    "            if k_ < 0:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        s=sum(chalk)\n",
    "        m=k%s\n",
    "        c=0\n",
    "        for i in range(len(chalk)):\n",
    "            c+=chalk[i]\n",
    "            if c>m:\n",
    "                return i\n",
    "                break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        i = 0 \n",
    "        n = len(chalk)\n",
    "        tot = sum(chalk) \n",
    "        k = k % tot \n",
    "        while k >= chalk[i]:\n",
    "            k -= chalk[i] \n",
    "            i = (i+1) % n\n",
    "        return i  \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk, k):\n",
    "        k %= sum(chalk)\n",
    "        if k == 0: return 0\n",
    "        for i, num in enumerate(chalk):\n",
    "            k -= num\n",
    "            if k < 0: return i\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        s=sum(chalk)\n",
    "        m=k%s\n",
    "        c=0\n",
    "        for i in range(len(chalk)):\n",
    "            c+=chalk[i]\n",
    "            if c>m:\n",
    "                return i\n",
    "                break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        mod = k % sum(chalk)\n",
    "        for i, num in enumerate(chalk):\n",
    "            if num > mod:\n",
    "                return i\n",
    "            mod -= num\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        S = sum(chalk)\n",
    "        k %= S\n",
    "        for i in range(len(chalk)):\n",
    "            if k >= chalk[i]:\n",
    "                k -= chalk[i]\n",
    "            else:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        k %= sum(chalk)\n",
    "        for i in range(len(chalk)):\n",
    "            if chalk[i] <= k:\n",
    "                k -= chalk[i]\n",
    "            else:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        allcnt = 0\n",
    "        for c in chalk:\n",
    "            allcnt += c\n",
    "        k %= allcnt\n",
    "        for i in range(len(chalk)):\n",
    "            if k < chalk[i]:\n",
    "                return i\n",
    "            k -= chalk[i]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        res_k = k % sum(chalk)\n",
    "        if res_k == 0 or chalk[0] >= res_k:\n",
    "            return 0\n",
    "\n",
    "        for i in range(1, len(chalk)-1):\n",
    "            chalk[i] += chalk[i-1]\n",
    "            if chalk[i] > res_k:\n",
    "                return i\n",
    "        return len(chalk)-1\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        # l, r = 0, len(chalk)-1\n",
    "        # while l < r:\n",
    "        #     mid = (r-l)//2+l\n",
    "        #     if chalk[mid] > res_k:\n",
    "        #         if mid!=0 and chalk[mid-1] <= res_k:\n",
    "        #             return mid\n",
    "        #         else:\n",
    "        #             r = mid\n",
    "        #     else:\n",
    "        #         l = mid+1\n",
    "        # return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        total = sum(chalk)\n",
    "        k = k % total\n",
    "\n",
    "        index = 0\n",
    "        for num in chalk:\n",
    "            if k < num:\n",
    "                return index\n",
    "            else:\n",
    "                k -= num\n",
    "            index += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        tot = sum(chalk)\n",
    "        k = k % tot\n",
    "        i, n = 0, len(chalk)\n",
    "        while k >= 0:\n",
    "            if k < chalk[i]:\n",
    "                return i\n",
    "            k -= chalk[i]\n",
    "            i = (i + 1) % n\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        k %= sum(chalk)\n",
    "        for i, c in enumerate(chalk):\n",
    "            if c > k:\n",
    "                return i \n",
    "            k -= c \n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        total = sum(chalk)\n",
    "        k %= total\n",
    "        ans = -1\n",
    "        for i, cha in enumerate(chalk):\n",
    "            if cha > k:\n",
    "                ans = i\n",
    "                break\n",
    "            k -= cha\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        k %= sum(chalk)\n",
    "        res = -1\n",
    "        for i, v in enumerate(chalk):\n",
    "            if v > k:\n",
    "                res = i\n",
    "                break\n",
    "            k -= v\n",
    "        return res\n",
    "\n",
    "        # l, r = 0, len(chalk)\n",
    "        # while l < r:\n",
    "        #     m = (l + r) // 2\n",
    "        #     if sum(chalk[:m]) > k:\n",
    "        #         r = m\n",
    "        #     else:\n",
    "        #         l = m + 1\n",
    "        # return l-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        s = sum(chalk)\n",
    "        a, k = divmod(k, s)\n",
    "        for i in range(len(chalk)):\n",
    "            if k < chalk[i]:\n",
    "                return i \n",
    "            k -= chalk[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        n = len(chalk)\n",
    "        s = sum(chalk)\n",
    "        i, cnt =0, 0\n",
    "        k = k % s\n",
    "        while k >= 0:\n",
    "            k -= chalk[i]\n",
    "            i += 1\n",
    "        return i - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        sum1 = sum(chalk)\n",
    "        k %= sum1 \n",
    "        while True:\n",
    "            for i,v in enumerate(chalk):\n",
    "                if k < v:\n",
    "                    return i\n",
    "                k-=v\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        i = 0\n",
    "        k %= sum(chalk)\n",
    "        while True:\n",
    "            k -= chalk[i]\n",
    "            if k >= 0:\n",
    "                i = 0 if i >= len(chalk) - 1 else i + 1\n",
    "            else:\n",
    "                break\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        # 计算所有学生一轮所需的粉笔总数\n",
    "        total = sum(chalk)\n",
    "        \n",
    "        # k模total就是最后一轮开始时剩余的粉笔数\n",
    "        k %= total\n",
    "        \n",
    "        # 按照学生的顺序消耗粉笔\n",
    "        for i, ch in enumerate(chalk):\n",
    "            if k < ch:\n",
    "                return i\n",
    "            k -= ch\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        n = len(chalk)\n",
    "        # presum = list(accumulate(chalk))\n",
    "\n",
    "        # rest = k % presum[-1]\n",
    "        # way one\n",
    "        # l, r = 0, n\n",
    "        # while l < r:\n",
    "        #     mid = (r + l) // 2\n",
    "        #     if presum[mid] > rest:\n",
    "        #         r = mid\n",
    "        #     else:\n",
    "        #         l = mid + 1\n",
    "        \n",
    "        # return l\n",
    "        # way two \n",
    "        # for i in range(n):\n",
    "        #     if rest - presum[i] < 0:\n",
    "        #         return i\n",
    "        tot = sum(chalk)\n",
    "        rest = k % tot \n",
    "\n",
    "        for i in range(n):\n",
    "            rest -= chalk[i]\n",
    "            if rest < 0:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        # 超时\n",
    "        # nindex = 0\n",
    "        # nl = len(chalk)\n",
    "        # while True:\n",
    "        #     if chalk[nindex] > k:\n",
    "        #         return nindex\n",
    "        #     k = k - chalk[nindex]\n",
    "        #     nindex = (nindex + 1) % nl\n",
    "        nl = len(chalk)\n",
    "        res = [0 for i in range(0, nl+1)]\n",
    "        for i in range(1, nl+1):\n",
    "            res[i] = res[i-1] + chalk[i-1]\n",
    "            if res[i] > k:\n",
    "                return i-1\n",
    "        \n",
    "        k = k % res[-1]\n",
    "\n",
    "        for i in range(0, nl+1):\n",
    "            if res[i] > k:\n",
    "                return i-1\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "      k %= sum(chalk)\n",
    "\n",
    "      for i, x in enumerate(chalk):\n",
    "        if k < x:\n",
    "          return i\n",
    "        k -= x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(n, chalk: List[int], k: int) -> int:\n",
    "        total=sum(chalk)\n",
    "        k%=total\n",
    "        out=0\n",
    "        S=0\n",
    "        for i,s in enumerate(chalk):\n",
    "            S+=s\n",
    "            if S>k:\n",
    "                out=i\n",
    "                break\n",
    "        return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        s = sum(chalk)\n",
    "        t = k % s\n",
    "        for i in range(len(chalk)):\n",
    "            t -= chalk[i]\n",
    "            if t < 0:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "      s=sum(chalk)\n",
    "      c=k//s\n",
    "      k-=c*s\n",
    "      i=0\n",
    "      n=len(chalk)\n",
    "      while k>=0:\n",
    "        k-=chalk[i%n]\n",
    "        i+=1\n",
    "      return (i-1)%n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        k=k%sum(chalk)\n",
    "        for i in range(len(chalk)):\n",
    "            if k<chalk[i]:\n",
    "                return i\n",
    "            else:\n",
    "                k-=chalk[i]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        res_k = k % sum(chalk)\n",
    "        if res_k == 0:\n",
    "            return 0\n",
    "\n",
    "        for i in range(1, len(chalk)-1):\n",
    "            chalk[i] += chalk[i-1]\n",
    "\n",
    "        l, r = 0, len(chalk)-1\n",
    "        while l < r:\n",
    "            mid = (r-l)//2+l\n",
    "            if chalk[mid] > res_k:\n",
    "                if mid!=0 and chalk[mid-1] <= res_k:\n",
    "                    return mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        n = len(chalk)\n",
    "        for i in range(1, n):\n",
    "            chalk[i] += chalk[i-1]\n",
    "        rest = k % chalk[-1]\n",
    "        return bisect_right(chalk, rest)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        n=len(chalk)\n",
    "        for i in range(n):\n",
    "            chalk[i]=chalk[0] if i==0 else chalk[i-1]+chalk[i]\n",
    "        k=k%chalk[-1]\n",
    "        for i in range(n):\n",
    "            if chalk[i]>k:return i\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        res_k = k % sum(chalk)\n",
    "        if res_k == 0 or chalk[0] >= res_k:\n",
    "            return 0\n",
    "        for i in range(1, len(chalk)-1):\n",
    "            chalk[i] += chalk[i-1]\n",
    "        #     if chalk[i] > res_k:\n",
    "        #         return i\n",
    "        # return len(chalk)-1\n",
    "\n",
    "\n",
    "        l, r = 0, len(chalk)-1\n",
    "        while l < r:\n",
    "            mid = (r-l)//2+l\n",
    "            if chalk[mid] > res_k:\n",
    "                if mid!=0 and chalk[mid-1] <= res_k:\n",
    "                    return mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        n = len(chalk)\n",
    "        for i in range(1, n):\n",
    "            chalk[i] += chalk[i-1]\n",
    "        rest = k % chalk[-1]\n",
    "        return bisect_right(chalk, rest)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        n=len(chalk)\n",
    "        for i in range(n):\n",
    "            chalk[i]=chalk[0] if i==0 else chalk[i-1]+chalk[i]\n",
    "        k=k%chalk[-1]\n",
    "        for i in range(n):\n",
    "            if chalk[i]>k:return i\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        n = len(chalk)\n",
    "        for i in range(1, n):\n",
    "            chalk[i] = chalk[i-1] + chalk[i]\n",
    "        k %= chalk[-1]\n",
    "        # 二分寻找 > k\n",
    "        l = 0\n",
    "        r = n - 1\n",
    "        while l <= r:\n",
    "            mid = (l+r) // 2\n",
    "            if chalk[mid] <= k:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "import itertools\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: list[int], k: int) -> int:\n",
    "        s = list(itertools.accumulate(chalk))\n",
    "        k %= s[-1]\n",
    "        return bisect.bisect_right(s, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        sum_num = 0\n",
    "        pre = []\n",
    "        for i in chalk:\n",
    "            sum_num += i\n",
    "            pre.append(sum_num)\n",
    "        k = k%sum_num\n",
    "\n",
    "        left = 0\n",
    "        right = len(chalk)-1\n",
    "        while left<=right:\n",
    "            mid = (left+right)>>1\n",
    "            if pre[mid] <= k:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid -1\n",
    "        return left\n",
    "        # for i in range(len(chalk)):\n",
    "        #     k = k-chalk[i]\n",
    "        #     if k<0:\n",
    "        #         return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        presum = []\n",
    "        for num in chalk:\n",
    "            if(len(presum) == 0):\n",
    "                presum.append(num)\n",
    "            else:\n",
    "                presum.append(presum[-1]+num)\n",
    "        tsum = presum[-1]\n",
    "        k = k % tsum\n",
    "        left, right = 0, len(presum)\n",
    "        while(left <= right):\n",
    "            mid = (left+right)//2\n",
    "            if(presum[mid] <= k):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 前缀和+二分查找\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        prefix = list(accumulate(chalk))\n",
    "        sum_ = prefix[-1]\n",
    "        if sum_ <= k:\n",
    "            k = k % sum_\n",
    "        return bisect_right(prefix, k)    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        s = list(accumulate(chalk))\n",
    "        k %= s[-1]\n",
    "        return bisect_right(s, k)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        prefixSum = [0] * len(chalk)\n",
    "        for i in range(len(prefixSum)):\n",
    "            if i == 0:\n",
    "                prefixSum[i] = chalk[i]\n",
    "            else:\n",
    "                prefixSum[i] = prefixSum[i-1] + chalk[i]\n",
    "        n = k % prefixSum[-1]\n",
    "        for i in range(len(prefixSum)):\n",
    "            if prefixSum[i] > n:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        n = len(chalk)\n",
    "        f = [0] * n\n",
    "        f[0] = chalk[0]\n",
    "        for i in range(n):\n",
    "            f[i] = f[i - 1] + chalk[i]\n",
    "        k %= f[n - 1]\n",
    "        for i in range(n):\n",
    "            if k < f[i]:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import operator\n",
    "class Solution:\n",
    "    def chalkReplacer(self, chalk: List[int], k: int) -> int:\n",
    "        return bisect_right((presum:=list(accumulate(chalk,operator.add))), k % presum[-1])\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
